package insertsort;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author tongchen
 * @create 2022-11-16 11:33
 */
public class sortBlog {
    public static void main(String[] args) {

        int[] arr = {9, 8, 7, 6, 4, 5, 3, 2, 1};//5655????
        //mergeSort(arr,0, arr.length-1);
        // mergeSortItr(arr);
        //使用基数排序
        //baseSort(arr);
        //使用冒泡排序
        // bubbleSort(arr);
        //  quickSort(arr,0,arr.length-1);
        //selectSort(arr);
        //insertSort(arr);
       // shellSort(arr);
        //bubbleSort(arr);
        //heapSort(arr);
      //  quickSort(arr,0, arr.length-1);
        //quickSortItr(arr);
        //mergeSort(arr,0, arr.length-1);
        mergeSortItr(arr);
        System.out.println(Arrays.toString(arr));

    }

    //1.选择排序
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; ++i) {
            //数组长度为arr.length,我们只需要比较arr.lengnth-1次，剩下的一定是最后最大或者最小的元素
            //按照升序排序不断去找最小值
            int minIndex = findMinIndex(arr, i);
            //将最小值进行交换
            swap(arr, i, minIndex);
        }

    }

    private static void swap(int[] arr, int i, int minIndex) {
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }

    private static int findMinIndex(int[] arr, int i) {
        //从i开始找最小值
        int minIndex = i;
        for (int j = i + 1; j < arr.length; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        return minIndex;

    }

    //2.插入排序
    //当我们向对一个数组进行升序排列，而如果数组本身已经是升序排列，这时我们不难发现的是，此时所有的数据只需要向前与其前一个数字进行比较，此时
    //时间复杂度为O（n）
    public static void insertSort(int[] arr) {
        //使用插入排序时，本轮数组开始的下标之前数组已经完全有序
        for (int i = 1; i < arr.length; ++i) {
            //将要比较的值暂存起来
            int temp = arr[i];
            //从i的前一个值往前进行比较
            int j = i - 1;
            while (j >= 0) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j];
                    j--;
                }
                //如果当前值小于等于arr[i]，说明arr[i]已经找到该存放的位置，此时跳出循环

                else {
                    break;
                }
            }
            //将arr[i]的值进行替换
            arr[j + 1] = temp;
        }

    }

    /**
     * 希尔排序是根据插入排序的数组越有序排序速度越快的特点，首先对数组进行预排序，即如果是在升序排序中，使小数尽量排在前面，使大数尽量
     * 排在后面，提高最后一次排序的速度
     *
     * @param arr：要排序的数组
     */
    //3.希尔排序
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        //只有gap等于1进行的排序同于完全的插入排序，其余的均是预排序
        while (gap >= 1) {
            shellCore(arr, gap);
            //更新gap
            gap /= 2;
        }
    }

    private static void shellCore(int[] arr, int gap) {
        //从gap下标开始排序，直到最后一个元素
        for (int i = gap; i < arr.length; ++i) {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0) {
                if (arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                } else {
                    break;
                }
            }
            arr[j + gap] = temp;
        }

    }
    //4.冒泡排序
    public static void bubbleSort(int[]arr){
        //共arr.length个元素，需要比较arr.length-1次
        for(int i=0;i< arr.length-1;++i){
            //设置标志值
            boolean flag=false;
            for(int j=0;j< arr.length-1-i;++j){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=true;
                }
            }
            if(flag==false){
                break;
            }
        }
    }
    //5.堆排序
    public static void heapSort(int[]arr){
        //创建堆
        createHeap(arr);
        //进行堆排序
        heapSortCore(arr);
    }

    private static void heapSortCore(int[] arr) {
        //定义end结点使其不断与根结点进行交换
        int end=arr.length-1;
        while(end>0){//当end==0时，说明其余元素都已经排好，也就不需要在进行最后一次排序
            swap(arr,0,end);
            //这时向下调整时，边界是end为下标的结点,也就是说不需要再考虑end结点的轮换问题（就大跟堆而言，根结点一直是最大的元素）
            shiftDown(arr,0,end);
            end--;
        }


    }

    private static void createHeap(int[] arr) {
        //定义最后一个父节点的坐标
        int parent=(arr.length-1-1)/2;
        //循环实现堆
        while (parent>=0){
            //不断向下遍历
            shiftDown(arr,parent, arr.length);
            parent--;
        }
    }

    private static void shiftDown(int[] arr, int parent,int end) {
        int child=2*parent+1;//默认左子节点为最大子节点
        while (child<end){
            //进行左右节点的比较
            if(child+1< end){//确保右结点存在
                if(arr[child]<arr[child+1]){
                    child+=1;//最大子节点进行轮换
                }
            }
            //将最大子节点与父节点进行比较
            if(arr[parent]<arr[child]){
                swap(arr,child,parent);
            }
            //父子节点不断向下进行遍历
            parent=child;
            child=2*parent+1;
        }
    }

    /**
     * 快速排序的核心思想是在数组内定义中间值，在中间值的左右范围内使比中间值小的元素放在其左边，比中间值大的元素放在其右边
     * @param arr:进行排序的数组
     * @param left：排序的左边界
     * @param right：排序的右边界
     */
    //6.快速排序
    //6.1快速排序的递归实现
    public static void quickSort(int[]arr,int left,int right){
        //对左右边界的有效性进行校验
        if(left>=right){
            return ;
        }
        int len=quickSortCoreDig(arr,left, right);
        //对左半部分进行递归
        quickSort(arr,left,len-1);
        //对右半部分进行递归
        quickSort(arr,len+1,right);


    }

    /**
     * 快速排序的核心实现方法1：hoare法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int quickSortCore(int[] arr, int left, int right) {
        //定义基准值
        int standardIndex=left;
        int standard=arr[left];
        while (left<right){
            //从右节点向左找比基准值小的值
            while(left<right&&arr[right]>=standard){
                right--;
            }
            while(left<right&&arr[left]<=standard){
                left++;
            }
            //左右节点值的交换
            swap(arr,left,right);
        }
        //当左右节点走到同一个值的时候将standard和这个下标的值进行交换
        swap(arr,standardIndex,left);
        return left;//返回中间结点的值，left或者right都可以
    }
    //快速排序的核心实现方法2：挖坑法
    public static int quickSortCoreDig(int[]arr,int left,int right){
        //首先定义一个基准值
        int standard=arr[left];
        //左右节点向彼此方向寻找
        while(left<right){
            while(left<right&&arr[right]>=standard){
                right--;
            }
            //右下标找到的数字放在左下标
            arr[left]=arr[right];
            //左子节点向右寻找
            while(left<right&&arr[left]<=standard){
                left++;
            }
            //左下标找到的值放到右下标
            arr[right]=arr[left];
        }
        //两个下标交汇时，我们将基准值放入其中
        arr[left]=standard;
        //返回中间结点（左右结点交汇，返回一个即可）、
        return left;

    }
    //两个
    //6.2快速排序的迭代实现
    public static void quickSortItr(int[]arr){
        //设计思想与递归完全相同，栈中存放的是左右两半部分或者多部分
        //创建栈空间
        Stack<Integer>stack=new Stack<>();
        int left=0;
        int right=arr.length-1;
        int len=quickSortCore(arr,left, right);
        if(left<len-1){
            stack.push(left);
            stack.push(len-1);
        }
        if(right>len+1){
            stack.push(len+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
             len=quickSortCore(arr,left, right);
            if(left<len-1){
                stack.push(left);
                stack.push(len-1);
            }
            if(right>len+1){
                stack.push(len+1);
                stack.push(right);
            }

        }
    }
    //7.归并排序的实现
    //7.1归并排序的递归实现
    public static void mergeSort(int[]arr,int left,int right){
        //对终止条件进行校验
        if(left>=right){
            return;
        }
        //求中间结点
        int mid=(left+right)/2;
        //对左部分和右部分进行递归分解
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        //对已经分解好的数组进行归并操作
        merge(arr,left,mid,right);
    }
    //归并排序的实现方法二:迭代
    public static void mergeSortItr(int[]arr){
        //定义步长
        int gap=1;
        //定义迭代的终止条件
        while(gap< arr.length){
            //i是分组后的第一个元素
            for (int i=0;i< arr.length;i+=2*gap){
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //修正mid和right的值防止越界
                if(mid>= arr.length){
                    mid=arr.length-1;
                }
                if(right>=arr.length){
                    right=arr.length-1;
                }
                //进行归并操作
                merge(arr,left,mid,right);
            }
            //将gap迭代
            gap*=2;
        }

    }
//归并排序的合并操作
    private static void merge(int []arr,int left, int mid, int right) {
        //建立一个额外空间的数组
        int[]tmp=new int[right-left+1];
        //将范围内的数组分解为两部分,依次进行比较并加入数组
        //定义两个下标作为遍历的指标
        int leftIndex=left;
        int rightIndex=mid+1;
        //定义index作为遍历数组的下标
        int index=0;
        while(leftIndex<=mid&&rightIndex<=right){
            if(arr[leftIndex]<arr[rightIndex]){
                tmp[index++]=arr[leftIndex++];
            }
            else {
                tmp[index++]=arr[rightIndex++];
            }
        }
        //对剩余数组进行合并
        while(leftIndex<=mid){
            tmp[index++]=arr[leftIndex++];
        }
        while(rightIndex<=right){
            tmp[index++]=arr[rightIndex++];
        }
        //最后将临时数组合并到原本数组
        for(int i=0;i< tmp.length;++i){
            arr[left+i]=tmp[i];
        }
    }

}

